public class Test8 {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 2];
        for(int i = 1;i < m + 1;i++)
            for(int j = 0;j < n + 2;j++)
                dp[i][j] = 10000;
        for(int i = 0;i < m + 1;i++) {
            for (int j = 0; j < n + 2; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++) {
                dp[i][j] = Math.min((Math.min(dp[i - 1][j - 1],dp[i - 1][j])),dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
            }
        }
        for(int i = 0;i < m + 1;i++) {
            for (int j = 0; j < n + 2; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        Test8 test8 = new Test8();
        int[][] arr = {{2,1,3},{6,5,4},{7,8,9}};
        int n = test8.minFallingPathSum(arr);
        System.out.println(n);
    }
}
